package com.shigi.knapsack.solvers;

import com.shigi.knapsack.KnapsackInstance;
import com.shigi.knapsack.KnapsackItem;
import com.shigi.knapsack.KnapsackSolution;
import com.shigi.knapsack.KnapsackSolver;

/**
 * Created by Miroslav Šiagi on 03/11/14.
 */
public class DynamicProgrammingValue implements KnapsackSolver {

    private KnapsackSolution knapsackSolution;
    private KnapsackInstance knapsackInstance;
    private KnapsackItem[] knapsackItems;

    public DynamicProgrammingValue() {}

    public KnapsackSolution solve(KnapsackInstance knapsackInstance) {
        this.knapsackInstance = knapsackInstance;
        this.knapsackSolution = new KnapsackSolution(knapsackInstance.getId());
        this.knapsackSolution.setNumberOfItems(knapsackInstance.getNumberOfItems());
        this.knapsackItems = this.knapsackInstance.getKnapsackItems();

        createSolution();

        this.knapsackSolution.setNumberOfItems(this.knapsackItems.length);
        return this.knapsackSolution;
    }

    private void createSolution() {
        int numberOfItems = this.knapsackItems.length;
        int maxWeight = this.knapsackInstance.getTotalWeight();
        int totalValue = getTotalValueOfItems(this.knapsackItems);

        int[][] matrixW = new int[numberOfItems+1][totalValue+1];

        for (int i = 0; i <= numberOfItems; i++) {
            // the lowest row init
            matrixW[i][0] = 0;
        }

        // init first column
        for (int c_iter = 1; c_iter <= totalValue; c_iter++) {
            matrixW[0][c_iter] = Integer.MAX_VALUE;
        }

        for (int i = 1; i <= numberOfItems; i++) {
            for(int c_iter = 1; c_iter <= totalValue; c_iter++) {
                int firstOption = matrixW[i - 1][c_iter];

                int indexOfSecond = c_iter - this.knapsackItems[i - 1].getValue();
                int partOfSecond = (indexOfSecond < 0) ? Integer.MAX_VALUE : matrixW[i - 1][indexOfSecond];
                int secondOption = (partOfSecond == Integer.MAX_VALUE) ? Integer.MAX_VALUE : (partOfSecond + this.knapsackItems[i - 1].getWeight());

                matrixW[i][c_iter] = Math.min(firstOption, secondOption);

            }
        }

        for(int c_iter = totalValue; c_iter >= 0; c_iter--) {
            if(matrixW[numberOfItems][c_iter] <= maxWeight) {
                this.knapsackSolution.setTotalValue(c_iter);
                setOtherUsedItems(matrixW, numberOfItems, c_iter);
                break;
            }
        }

    }

    private void setOtherUsedItems(int[][] matrixW, int indexOfLastItem, int lastValue) {
        if(indexOfLastItem - 1 < 0 || lastValue == 0) {
            this.knapsackSolution.setUsedItems(0);
            return;
        }

        while(matrixW[indexOfLastItem][lastValue] == matrixW[indexOfLastItem-1][lastValue]) {
            indexOfLastItem--;
        }

        this.knapsackSolution.setUsedItems((int) (this.knapsackSolution.getUsedItems() + Math.pow(2, (double)this.knapsackInstance.getNumberOfItems() - 1 - this.knapsackItems[indexOfLastItem - 1].getId())));
        this.knapsackItems[indexOfLastItem - 1].setUsed(true);

        indexOfLastItem--;
        if(indexOfLastItem < 1) {
            return;
        }

        int nextValue = lastValue - this.knapsackInstance.getKnapsackItems()[indexOfLastItem-1].getValue();

        while(nextValue > 0) {
            while(indexOfLastItem > 0 && matrixW[indexOfLastItem][nextValue] == matrixW[indexOfLastItem-1][nextValue]) {
                indexOfLastItem--;
            }
            if(indexOfLastItem < 1) {
                return;
            }
            this.knapsackSolution.setUsedItems((int) (this.knapsackSolution.getUsedItems() + Math.pow(2, (double)this.knapsackInstance.getNumberOfItems() - 1 - this.knapsackItems[indexOfLastItem - 1].getId())));
            this.knapsackItems[indexOfLastItem - 1].setUsed(true);
            indexOfLastItem--;
            if(indexOfLastItem < 1) {
                return;
            }

            nextValue = nextValue - this.knapsackInstance.getKnapsackItems()[indexOfLastItem-1].getValue();
        }
    }

    private int getTotalValueOfItems(KnapsackItem[] knapsackItems) {
        int value = 0;
        for (int i = 0; i < knapsackItems.length; i++) {
            value += knapsackItems[i].getValue();
        }
        return value;
    }

}
